package tree;

import java.util.Scanner;
import java.util.TreeMap;

/**
 * 一、红黑树要满足的要求:
 * 1.每个节点不是红色就是黑色
 * 2.不可能有连在一起的红色节点
 * 3.根节点都是黑色
 * 4.每个红色节点的两个子节点都是黑色, 每个叶子节点都是黑色, 每个叶子节点都是额外添加的NaN节点。
 * 二、插入规则：
 * 1.插入节点默认为红色
 * 2.根节点为黑色
 * 三、变换规则：
 * 1.变颜色: 如果当前节点的父节点是红色，叔叔节点也是红色
 * 2.左旋: 如果当前节点的父节点是红色，叔叔节点为黑色，且当前节点为右子树
 * 3.右旋: 如果当前节点的父节点是红色，叔叔节点为黑色，且当前节点为左子树
 * @param <T>
 */
public class DRBTree<T extends Comparable<T>> {

    //根节点
    private RBNode<T> root;

    enum Color {
        RED, BLACK
    }


    public class RBNode<T extends Comparable<T>> {
        private Color color;
        private T key;
        private RBNode<T> parent;
        private RBNode leftChild;
        private RBNode rightChild;

        public RBNode(Color col, T key, RBNode parent, RBNode leftChild, RBNode rightChild) {
            this.color = col;
            this.key = key;
            this.parent = parent;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        public T getKey() {
            return this.key;
        }
    }


    public RBNode<T> parentOf(RBNode<T> node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }


    public Color colorOf(RBNode<T> node) {
        if (node != null) {
            return node.color;
        }
        return Color.BLACK;
    }


    public void setParent(RBNode<T> node, RBNode<T> parent) {
        if (node != null) {
            node.parent = parent;
        }
    }


    public void setColor(RBNode<T> node, Color color) {
        if (node != null) {
            node.color = color;
        }
    }

    public boolean isRed(RBNode<T> node) {
        return (node != null && node.color == Color.RED) ? true : false;
    }

    public boolean isBlack(RBNode<T> node) {
        return !isRed(node);
    }

    public void setRed(RBNode<T> node) {
        if (node != null) {
            node.color = Color.RED;
        }
    }

    public void setBlack(RBNode<T> node) {
        if (node != null) {
            node.color = Color.BLACK;
        }
    }

    //寻找为key值的节点
    public RBNode<T> search(T key, RBNode<T> node) {
        if (node != null) {
            int com = key.compareTo(node.key);
            if (com < 0) {
                return search(key, node.leftChild);
            } else if (com > 0) {
                return search(key, node.rightChild);
            } else {
                return node;
            }
        }
        return null;
    }

    //寻找后继节点，即大于该节点的最小节点
    public RBNode<T> min(RBNode<T> node) {
        if (node.leftChild == null) {
            return node;
        }
        while (node.leftChild != null) {
            node = node.leftChild;
        }
        return node;
    }

    public RBNode successor(RBNode<T> node) {
        if (node.rightChild != null) {
            return min(node.rightChild);
        }
        RBNode<T> y = node.parent;
        while ((y != null) && (y.rightChild == node)) {
            node = y;
            y = y.parent;
        }
        return y;
    }

    //对某个节点进行左旋
    public void leftRonate(RBNode<T> x) {
        RBNode<T> y = x.rightChild;
        if (y.leftChild != null) {
            y.leftChild.parent = x;
        }
        x.rightChild = y.leftChild;
        y.leftChild = x;
        y.parent = x.parent;
        if (x.parent != null) {
            if (x.parent.leftChild == x) {
                x.parent.leftChild = y;
            } else {
                x.parent.rightChild = y;
            }
        } else {
            this.root = y;
        }
        x.parent = y;
    }

    //对某个节点进行右旋
    public void rightRonate(RBNode<T> x) {
        RBNode<T> y = x.leftChild;
        if (y.rightChild != null) {
            y.rightChild.parent = x;
        }
        y.parent = x.parent;
        x.leftChild = y.rightChild;
        y.rightChild = x;
        if (x.parent != null) {
            if (x.parent.leftChild == x) {
                x.parent.leftChild = y;
            } else {
                x.parent.rightChild = y;
            }
        } else {
            this.root = y;
        }
        x.parent = y;
    }


    /**
     * 变换过程：
     * 1.变颜色:
     * (1)把父亲节点设为黑色
     * (2)把叔叔节点设为黑色
     * (3)把爷爷节点设为红色
     * (4)把指针指向爷爷节点，继续循环分析节点变换规则
     * 2.左旋
     * (1) 父节点作为左旋
     * 3.右旋
     * (1)把父亲节点设为黑色
     * (2)把爷爷节点设为红色
     * (3)以爷爷节点右旋
     */
    //红黑树添加修复
    public void insertFixUp(RBNode<T> node) {
        //TreeMap
        RBNode<T> parent, gparent;
        //当前节点的父节点为红色
        while (((parent = parentOf(node)) != null) && isRed(parent)) {
            gparent = parentOf(parent);
            //获取叔叔节点：存在叔叔节点，在左边和在右边的情况
            if (gparent.leftChild == parent) {
                RBNode<T> uncle = gparent.rightChild;
                //叔叔节点为红色
                if (isRed(uncle)) {//变颜色规则
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    //当前节点指向爷爷
                    node = gparent;
                } else {//旋转
                    //且当前节点为右子树
                    if (parent.rightChild == node) {
                        leftRonate(parent);
                        RBNode<T> temp = node;
                        //当前节点指向父节点
                        node = parent;
                        //此时的父节点为 当前节点
                        parent = temp;
                    }
                    setBlack(parent);
                    setRed(gparent);
                    rightRonate(gparent);
                }
            } else {
                RBNode<T> uncle = gparent.leftChild;
                if (isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    //当前节点指向爷爷
                    node = gparent;
                } else {
                    if (parent.leftChild == node) {
                        rightRonate(parent);
                        RBNode<T> temp = node;
                        //当前节点指向父节点
                        node = parent;
                        //此时的父节点为 当前节点
                        parent = temp;
                    }
                    setBlack(parent);
                    setRed(gparent);
                    leftRonate(gparent);
                }
            }
        }

        //规范： 根节点为 黑色
        setBlack(root);
    }

    //红黑树删除修复
    public void deleteFixUp(RBNode<T> node, RBNode<T> parent) {
        RBNode<T> other;
        while (isBlack(node) && node != this.root) {
            if (parent.leftChild == node) {
                other = parent.rightChild;
                if (isRed(other)) {
                    setRed(parent);
                    setBlack(other);
                    leftRonate(parent);
                    continue;
                } else {
                    if (isBlack(other.leftChild) && isBlack(other.rightChild)) {
                        setRed(other);
                        node = parent;
                        parent = parentOf(node);
                    } else if (isRed(other.leftChild) && isBlack(other.rightChild)) {
                        setRed(other);
                        setBlack(other.leftChild);
                        rightRonate(other);
                    } else if (isRed(other.rightChild)) {
                        setColor(other, colorOf(parent));
                        setBlack(parent);
                        setBlack(other.rightChild);
                        leftRonate(parent);
                        break;
                    }
                }
            } else {
                other = parent.leftChild;
                if (isRed(other)) {
                    setBlack(other);
                    setRed(parent);
                    rightRonate(parent);
                    continue;
                } else {
                    if (isBlack(other.leftChild) && isBlack(other.rightChild)) {
                        setRed(other);
                        node = parent;
                        parent = parentOf(node);
                    } else if (isRed(other.rightChild) && isBlack(other.leftChild)) {
                        setRed(parent);
                        setBlack(other.rightChild);
                        leftRonate(other);
                    } else if (isRed(other.leftChild)) {
                        setColor(other, colorOf(parent));
                        setBlack(parent);
                        setBlack(other.leftChild);
                        rightRonate(parent);
                        break;
                    }
                }
            }
        }
        setBlack(node);
    }


    //红黑树添加操作
    private void insert(RBNode<T> node) {
        int com;
        RBNode<T> x = this.root;
        RBNode<T> xtmp = null;
        //查找node的父节点
        while (x != null) {
            xtmp = x;
            com = node.key.compareTo(x.key);
            if (com < 0) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        node.parent = xtmp;
        if (xtmp == null) {
            //如果父节点为空那么,将node作为根节点
            this.root = node;
        } else {
            //将node 插入到父节点
            com = node.key.compareTo(xtmp.key);
            if (com < 0) {
                xtmp.leftChild = node;
            } else {
                xtmp.rightChild = node;
            }
        }
        //修复
        insertFixUp(node);
    }

    public void insert(T key) {
        //规范： 插入节点默认为 红色
        insert(new RBNode<T>(Color.RED, key, null, null, null));
    }

    //红黑树删除操作
    public void delete(RBNode<T> node) {
        RBNode<T> child, parent, replace;
        Color color = Color.RED;
        if (node.leftChild != null && node.rightChild != null) {
            replace = successor(node);
            parent = parentOf(replace);
            child = replace.rightChild;
            color = colorOf(replace);
            if (node == parentOf(replace)) {
                parent = replace;
            } else {
                if (child != null) {
                    setParent(child, parentOf(replace));
                }
                replace.parent.leftChild = child;
                replace.rightChild = node.rightChild;
                setParent(node.rightChild, replace);
            }
            setParent(replace, parentOf(node));
            replace.leftChild = node.leftChild;
            setParent(node.leftChild, replace);
            setColor(replace, colorOf(node));
            if (parentOf(node) != null) {
                if (node.parent.leftChild == node) {
                    node.parent.leftChild = replace;
                } else {
                    node.parent.rightChild = replace;
                }
            } else {
                this.root = replace;
            }
            if (color == Color.BLACK) {
                deleteFixUp(child, parent);
            }
        } else {
            if (node.leftChild != null) {
                replace = node.leftChild;
            } else {
                replace = node.rightChild;
            }
            parent = parentOf(node);
            if (parent != null) {
                if (parent.leftChild == node) {
                    parent.leftChild = replace;
                } else {
                    parent.rightChild = replace;
                }
            } else {
                this.root = replace;
            }
            setParent(replace, parent);
            color = colorOf(node);
            child = replace;
            if (color == Color.BLACK) {
                deleteFixUp(child, parent);
            }
        }

    }

    public void delete(T key) {
        RBNode<T> node;
        if ((node = search(key, this.root)) != null) {
            delete(node);
        }
    }

    public printDelegate print() {
        return new printDelegate();
    }


    class printDelegate {
        public void preOrder() {
            preOrder(root);
        }

        public void inOrder() {
            inOrder(root);
        }

        public void postOrder() {
            postOrder(root);
        }

        public void printTree() {
            printTree(root);
        }

        public void print() {
            print(root, 0);
        }


        //前序遍历
        public void preOrder(RBNode<T> node) {
            if (node != null) {
                System.out.print(node.key + " ");
                preOrder(node.leftChild);
                preOrder(node.rightChild);
            }
        }

        //中序遍历
        public void inOrder(RBNode<T> node) {
            if (node != null) {
                inOrder(node.leftChild);
                System.out.print(node.key + " ");
                inOrder(node.rightChild);
            }
        }

        //后序遍历
        public void postOrder(RBNode<T> node) {
            if (node != null) {
                postOrder(node.leftChild);
                postOrder(node.rightChild);
                System.out.print(node.key + " ");
            }
        }

        public void printTree(RBNode head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }

        private void printInOrder(RBNode head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.rightChild, height + 1, "v", len);
            String val = to + head.key + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.leftChild, height + 1, "^", len);
        }

        private String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }

        //打印红黑树
        public void print(RBNode<T> node, int direction) {
            if (node != null) {
                if (direction == 0) {
                    System.out.printf("%2d(%s) is root\n", node.key, node.color);
                } else {
                    System.out.printf("%2d(%s) is %s child 父节点 %2d\n", node.key, node.color, direction == -1 ? "left" : "right", node.parent.key);
                }
                print(node.leftChild, -1);
                print(node.rightChild, 1);
            }
        }
    }


    public static void main(String[] args) {
        mian2();
    }

    public static void mian2() {
        DRBTree<Integer> tree = new DRBTree<Integer>();
        int[] a = {10, 20, 30, 40, 50, 60, 70, 80, 90,40,40};
        //红黑树添加测试
        for (int i = 0; i < a.length; i++) {
            tree.insert(a[i]);
        }
        tree.print().printTree();
    }

    public void mian1() {
        DRBTree<Integer> tree = new DRBTree<Integer>();
        int[] a = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        //红黑树添加测试
        for (int i = 0; i < a.length; i++) {
            tree.insert(a[i]);
        }
        System.out.print("前序遍历: ");
        tree.print().preOrder();
        System.out.print("\n中序遍历: ");
        tree.print().inOrder();
        System.out.print("\n后序遍历: ");
        tree.print().postOrder();
        System.out.println();
        tree.print().print();
        System.out.print("\n输入要删除的节点:");
        Scanner scan = new Scanner(System.in);
        int key = scan.nextInt();
        //红黑树删除测试
        tree.delete(key);
        System.out.println();
        tree.print().print();
    }
}
